package _02_linked_list.exerc.reverse;

import _02_linked_list.exerc.ListNode;
import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/2 - 15:25
 * 反转单向链表案例  leetcode 官方给出的是方法3，5
 */
public class MyTest {


    /**
     * 构建单向链表
     * @param size 链表大小
     * @return
     */
    ListNode init(int size) {
        ListNode head = null;
        ListNode tail = null;
        for (int i = 1; i <= size; i++) {
            ListNode t = new ListNode(i);
            if(head == null) {
                tail = head = t;
            } else {
                tail.next = t;
                tail = t;
            }
        }
        return head;
    }

    /**
     * 给出一个单向链表对象 ListNode，需要将其反转指向
     */
    @Test
    public void test1() {
        ListNode list = init(5);
        System.out.println(list);

//        System.out.println(foo1(list));
//        System.out.println(foo2(list));
//        System.out.println(foo3(list));
//        System.out.println(foo4(list));
        System.out.println(foo5(list));
    }

    /**
     * 方法5 （代码较少，内存占用较小，较容易懂，面向过程）
     * 提供两个指针 n，removedFirst
     *             n 指向新链表，默认值null
     *             removedFirst 指向需要移除节点的下一个节点，用于记录移除后的头节点
     *
     *         o 源链表
     *         n 新链表（返回值）
     */
    ListNode foo5(ListNode o) {
        if(o == null || o.next == null) {
            return o;
        }

        ListNode n = null;
        while (o != null) {
            ListNode removedFirst = o.next;
            o.next = n;
            n = o;
            o = removedFirst;
        }
        return n;
    }

    /*
        方法4
        提供两个指针 02,n1 （一开始都指向头节点）
        n1 表示头节点
        o2 表示每次需要断开插入到n1前面的节点

        n1
        o1
        1,2,3,4,5

        n1
            o1
        2,1,3,4,5

        n1
              o1
        3,2,1,4,5
     */
    ListNode foo4(ListNode o1) {
        if(o1 == null || o1.next == null) {
            return null;
        }
        ListNode o2 = o1.next;
        ListNode n1 = o1;
        while (o2 != null) {
            o1.next = o2.next;
            o2.next = n1;
            n1 = o2;
            o2 = o1.next;
        }
        return n1;
    }

    // 方法3
    // 递归实现，建议 debug 一步步看
    ListNode foo3(ListNode p) {
        if(p == null || p.next == null) {
            return p;
        }
        ListNode last = foo3(p.next);
        /*
            假设此时 last 是最后一链，那么 p 就是last的上一链
            p.next = last        p.next.next = last.next
            如果last = [5]  p = [4,5]
            p.next.next = p;  表示将5的next指向4，而4的next又指向5，循环引用
            p.next = null  就表示将4的next断开，循环引用就断开了，此时 last = [5,4]
         */
        p.next.next = p;
        // 1，防止死链  2，将循环引用断开，因此上面只需调用两次next即可得到p要插入的位置
        p.next = null;
        return last;
    }

    // 方法2
    // 创建二个容器，用于存储链表，将第一个容器中的链表头依次移动到第二个链表的头部
    ListNode foo2(ListNode head) {
        MyLinkedList list1 = new MyLinkedList(head);
        MyLinkedList list2 = new MyLinkedList(null);
        while (true) {
            ListNode removed = list1.removeFirst();
            if(removed == null) {
                break;
            }
            list2.addFirst(removed);
        }
        return list2.head;
    }

    // 方法1
    // 创建一个新链表，依次从尾部开始构建
    ListNode foo1(ListNode head) {
        ListNode newNode = null;
        ListNode p = head;
        while (p != null) {
            newNode = new ListNode(p.val, newNode);
            p = p.next;
        }
        return newNode;
    }
}
